package com.example.ten_sort_text.sort;


/**
 * 快速排序：
 * 1. 选择一个基准元素
 * 2. 将所有小于基准元素的元素放在基准元素左边
 * 3. 将所有大于基准元素的元素放在基准元素右边
 * 4. 递归地对左右两个分区进行以上步骤，直到各分区只有一个元素为止。
 *
 * 时间复杂度：O(nlog(n))
 * 空间复杂度：O(log(n))
 * 稳定性：不稳定
 */
public class FastSort {
    public static void main(String[] args) {
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        sort(arr,0,arr.length - 1);
        for (int i : arr){
            System.out.print(i + ";");
        }
    }


    public static void sort(int[] arr, int low, int hight){
        if(hight <= low){
            return;
        }
        Boolean flag = true; // 高位指针标识
        int start = low; //递归使用
        int end = hight;
        int mid = arr[low]; // 取出基准元素 低位空 不移动
        while(true){
            if (flag){
                // 低位空 高位指针移动
                if (arr[hight] > mid){
                    hight--;
                }else {
                    //将小于基准元素的元素放在低位为空的位置
                    arr[low] = arr[hight];
                    // 移动低位指针
                    low++;
                    flag = false;
                }
            }else {
                //低位指针移动
                if(arr[low] < mid){
                    low++;
                }else {
                    // 将大于基准元素的元素放在高位为空的位置
                    arr[hight] = arr[low];
                    // 移动高位指针
                    hight--;
                    flag = true;
                }
            }
            if (low == hight){
                // 高低位指针重合
                // 将基数放入
                arr[low] = mid;
                break;
            }
        }
        // 此时基数左边的数都小于基数 右边的数都大于基数
        //  递归排序基数左边的数组 和 基数右边的数组
        sort(arr, start, low-1);
        sort(arr, low+1, end);
    }
}
